package com.rgs.se.sort;




public class _1MergeSort {

    //合并
    public static void sort(int[] arr,int low,int mid,int high){
        int pa = low; //左侧首部
        int pb = mid+1;  //右侧首部
        int pt = 0;  //temp数组的首部
        int[] temp =new int[arr.length];
        /*谁小谁先进*/
        while(pa <= mid && pb <= high){
            if(arr[pa] <= arr[pb]){
                temp[pt] = arr[pa];
                pa++;
                pt++;
            }else{
                temp[pt] = arr[pb];
                pb++;
                pt++;
            }
        }
        /*第一个数组有剩余*/
        while(pa <= mid){
            temp[pt] = arr[pa];
            pa++;
            pt++;
        }
        /*第二个数组有剩余*/
        while(pb <= high){
            temp[pt] = arr[pb];
            pb++;
            pt++;
        }
        for (int i = 0; i < pt; i++) {
            arr[low + i] = temp[i];
        }

    }

    //分解
    public static void mergeSort(int[] arr,int p,int r){
        if(p<r){
            int mid = p+((r-p)>>1);
            mergeSort(arr,p,mid);
            mergeSort(arr,mid+1,r);
            sort(arr,p,mid,r);
        }
    }

    public static void main(String[] args) {
        int[] a = {2,7,3,9,6,15,8,18,10,25};
        SortUtil.Print(a);
        mergeSort(a,0,a.length-1);
        SortUtil.Print(a);
    }

}